#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stdlib.h>
#include<string>
using namespace std;

template<class K,class V>
class BinaryTreeNode
{
public:
	BinaryTreeNode<K,V>* Left;
	BinaryTreeNode<K,V>* Right;
	K _key;
	V _value;

	BinaryTreeNode(const K& key,const V& value)
		:Left(nullptr)
		, Right(nullptr)
		, _key(key)
		,_value(value)
	{}
};

template<class K,class V>
class BinarySerchTree
{
public:
	BinarySerchTree()
		:_root(nullptr)
	{}

	//非递归法建树
	bool Insert(const K& key,const V& value)
	{
		BinaryTreeNode<K,V>* cur = _root;
		BinaryTreeNode<K,V>* parent = _root;
		if (_root == nullptr)
		{
			_root = new BinaryTreeNode<K,V>(key,value);
			return true;
		}
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->Right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->Left;
			}
			else
			{
				return false;
			}
		}
		if (key < parent->_key)
		{
			cur = new BinaryTreeNode<K,V>(key,value);
			parent->Left = cur;
			return true;
		}
		else
		{
			cur = new BinaryTreeNode<K,V>(key,value);
			parent->Right = cur;
			return true;
		}
	}

	//递归法建树
	BinaryTreeNode<K,V>* InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}

	BinaryTreeNode<K,V>* _InsertR(BinaryTreeNode<K,V>*& root, const K& key,const V& value)
	{
		if (root == nullptr)
		{
			root = new BinaryTreeNode<K,V>(key,value);
			return root;
		}
		if (key > root->_key)
		{
			return _InsertR(root->Right, key);
		}
		else if (key < root->_key)
		{
			return _InsertR(root->Left, key);
		}
		else
		{
			return nullptr;
		}
	}

	BinaryTreeNode<K,V>* Find(const K& key)
	{
		BinaryTreeNode<K,V>* cur = _root;
		while (cur)
		{
			if (key > cur->_key)
				cur = cur->Right;
			else if (key < cur->_key)
				cur->Left;
			else
				return cur;
		}
		return nullptr;
	}

	//迭代删除法（最好）
	bool Erase(const K& key)
	{
		BinaryTreeNode<K,V>* cur = _root;
		BinaryTreeNode<K,V>* parent = _root;
		//查找删除节点
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->Right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->Left;
			}
			else
				goto isfind;
		}
		return false;
	isfind:
		if (cur->Left == nullptr)
		{
			if (cur == parent)
			{
				_root = cur->Right;
			}
			else if (key == parent->Left->_key)
			{
				parent->Left = cur->Right;
			}
			else
			{
				parent->Right = cur->Right;
			}
			delete cur;
		}
		else if (cur->Right == nullptr)
		{
			if (cur == parent)
			{
				_root = cur->Left;
			}
			else if (key == parent->Left->_key)
			{
				parent->Left = cur->Left;
			}
			else
			{
				parent->Right = cur->Left;
			}
			delete cur;
		}
		else
		{
			BinaryTreeNode<K>* ers = cur->Right;
			BinaryTreeNode<K>* pers = cur;
			while (ers->Left)
			{
				pers = ers;
				ers = ers->Left;
			}
			cur->_key = ers->_key;
			//判断ers在pers的左边还是右边
			if (ers == pers->Left)
				pers->Left = ers->Right;
			else
				pers->Right = ers->Right;
			delete ers;
		}
		return true;
	}

	//递归删除法
	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}

	bool _EraseR(BinaryTreeNode<K,V>*& root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (key < root->_key)
			return _EraseR(root->Left, key);
		else if (key > root->_key)
			return _EraseR(root->Right, key);
		else//找到要删除的结点
		{
			BinaryTreeNode<K,V>* del = root;//记录删除节点降地址
			if (root->Left == nullptr)
				root = root->Right;
			else if (root->Right == nullptr)
				root = root->Left;
			else//删除结点有两个孩子
			{
				BinaryTreeNode<K>* min = root->Right;
				while (min->Left)
				{
					min = min->Left;
				}
				std::swap(min->_key, root->_key);
				return _EraseR(root->Right, key);//交换值后复用递归删除，从root的右子树开始找。
			}
			delete del;
			return true;
		}
	}

	//重载[],返回该结点的value引用
	

	//中序遍历
	void InOder()
	{
		_InOder(_root);
		cout << endl;
	}

	void _InOder(BinaryTreeNode<K,V>* root)
	{
		if (root == nullptr)
			return;
		_InOder(root->Left);
		cout << root->_key << ":" << root->_value << endl;
		_InOder(root->Right);
	}

private:
	BinaryTreeNode<K,V>* _root;
};

int main()
{
	BinarySerchTree<string, string> BST;
	BST.Insert("章溢", "416之子");
	BST.Insert("徐少聪", "416之父");
	BST.Insert("邹涛", "416之舅");
	BST.Insert("李浩", "416之叔");
	BST.InOder();
	return 0;
}